875. 爱吃香蕉的珂珂 | Mkdir700的算法笔记

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

提示：

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/koko-eating-bananas

思路及分析

题目分析

从香蕉数组piles内每小时吃一堆，至于吃多少是K决定的；
如果K>piles[i]，则这堆香蕉piles[i]直接吃完，耗时1个小时
如果K<piles[i]，还会剩下piles[i]-K个香蕉，耗时1个小时

要求：

找到一个K值，使得珂珂能在H小时内吃完所有香蕉
K值要求最小

步骤分析

确定二分查找的范围

此题使用『二分查找』来解决，所以首先就要确定『二分查找』的范围，我们找到的是K值，根据题意，K的最大值不会超过香蕉数组的最大值，最小值就是每小时吃一个香蕉。

所以，K的查找范围是[1, max(piles)]

left, right = 1, max(piles)

寻找二分查找的条件

想一想我们选择的K最终需要满足的题意和谁有关？和时间H有关。

那么我们的思路就可以是，选择一个K，计算以当前速度（K）吃完所有香蕉的时间h

如果h大于H

说明珂珂吃的速度太慢（K值太小）导致花费的时间h大（h太大），所以提升珂珂的速度（使K变大），那么下一次二分查找的范围就是[k+1, right]

根据题目K值要求最小，意思就是我们要找到h最后一次小于H的K

k要求最小 => 时间花费尽可能长，但是不能超过H

那么，当h大于H时在决定下一次搜索区间的时候，就可以让k+1，这里要慢慢想想。

这道题因为时间与速度的关系，导致二分的条件有点绕。

如果h小于H

说明珂珂吃的速度太快（K值太大）导致花费的时间小（h太小），所以需要使得K变小，那么下一次二分查找的范围就是[left, k]

h小于H可能是正确答案，也可能不是，所以这里决定下一搜索区间时k不能加1

如果h等于H

此时，虽然时间一致，但是因为要求K值最小，所以仍不能确定此时k就是最终的答案，在处理下一次搜索区间时与h小于H的情况一致

速度等于`k`时吃完所有香蕉的时间

可视化珂珂吃香蕉的规则

还有一种更高效的方法(数学计算)

h = 0
for num in piles:
    h += (num + k - 1) // k

二分查找范围的优化

查找范围的右边界可以取min(piles)，需要满足以min(piles)的速度耗时大于H

否则范围就是是[1, min(piles)]

minn, maxn = min(piles), max(piles)
if judge(piles, minn) > H:
    left, right = minn, maxn
    else:
        left, right = 1, minn

完整代码

代码1：

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        left, right = 1, max(piles)
        size = len(piles)
        while left < right:
            k = (left + right) >> 1
            h = self.helper(piles, k)
            if h > H:
                left = k + 1
            else:
                right = k
        return left

    def helper(self, piles, k):
        res = 0
        for num in piles:
            res = res + (num + k - 1) // k
        return res

代码2(优化二分范围)

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
		minn, maxn = min(piles), max(piles)
        if self.helper(piles, minn) > H:
            left, right = minn, maxn
        else:
            left, right = 1, mixn
        while left < right:
            k = (left + right) >> 1
            h = self.helper(piles, k)
            if h > H:
                left = k + 1
            else:
                right = k
        return left

    def helper(self, piles, k):
        res = 0
        for num in piles:
            res = res + (num + k - 1) // k
        return res